The invention relates to computer aided design methods in general for structures in a variety of technical fields and in particular for semiconductor devices.
Many problems in engineering, physics and chemistry require to solve systems of partial differential equations of the type:                               ∇          →                ⁢                  ·                                    J              →                                      (              k              )                                          +                        ∂                      ρ                          (              k              )                                                ∂          t                      =          S              (        k        )              ;
k being a positive whole number
In this equation (equation 1), J represents a flux of a substance under consideration whose density is given by xcfx81 and S represents some external source/sink of the substance. To mention a few examples:
Electrical Engineering:
xcfx81 is the charge density,
J is the current density,
S is the external charge source (recombination, generation)
Structural Engineering
Computational Fluid Dynamics:
xcfx81(i)=u(i) the components of the fluid velocity field,
J(i)=Pxe2x88x92{fraction (xcexc/3)}∇.u(i) the pressure tensor,
S(i)={fraction (xcexc/xcfx81)}∇2u(i)+F(i)/m the external force,             ∂      ρ              ∂      t        →                    ∂        ρ                    ∂        t              +                  ∇        →            ⁢              ·                  u          →                    
xe2x80x83the convective derivative.
The list is not exhaustive and there exist many examples where problems are reformulated in such a form that their appearance is as in equation (1). An important example is the Laplace equation and Poisson equation, in which
{right arrow over (J)}={right arrow over (∇)}"psgr"
is the derivative of a scalar field.
There have been presented a number of methods for solving a set of partial differential equations as given above. All numerical methods start from representing the continuous problem by a discrete problem on a finite set of representative nodes in the domain where one is interested in the solution. In other words a mesh is generated in a predetermined domain. The domain can be almost anything ranging from at least a part of or a cross-section of a car to at least a part of or a cross-section of a semiconductor device. For clarification purposes, we limit the discussion here to two-dimensional domains and two-dimensional meshes. This mesh comprises nodes and lines connecting these nodes. As a result, the domain is divided into two-dimensional elements. The shape of the elements depends amongst others on the coordinate system which is chosen. If for example a Cartesian coordinate system is chosen, the two-dimensional elements are e.g. rectangles or triangles. Using such a mesh, the domain can be introduced in a computer aided design environment for optimization purposes. Concerning the mesh, one of the issues is to perform the optimization using the appropriate amount of nodes at the appropriate location. There is a minimum amount of nodes required in order to ensure that the optimization process leads to the right solution at least within predetermined error margins. On the other hand, if the total amount of nodes increases, the complexity increases and the optimization process slows down or even can fail. Because at the start of the optimization process, the (initial) mesh usually thus not comprise the appropriate amount of nodes, additional nodes have to be created or nodes have to be removed. Adding nodes is called mesh refinement whereas removing nodes is called mesh coarsening. Four methods are discussed. As stated above, for clarification and simplification purposes we use the xe2x80x98languagexe2x80x99 of two dimensions, but all statements have a translation to three or more dimensions.
The finite-difference method is the most straightforward method for putting a set of partial differential equations on a mesh. One divides the coordinate axes into a set of intervals and a mesh is constructed by all coordinate points and replaces the partial derivatives by finite differences. The method has the advantage that it is easy to program, due to the regularity of the mesh. The disadvantage is that during mesh refinement many spurious additional nodes are generated in regions where no mesh refinement is needed.
The finite-box method, as e.g. in A. F. Franz, G. A. Franz, S. Selberherr, C. Ringhofer and P. Markowich xe2x80x9cFinite Boxesxe2x80x94A Generalization of the Finite-Difference Method Suitable for Semiconductor Device Simulationxe2x80x9d IEEE Trans. on Elec. Dev. ED-30, 1070 (1983), is an improvement of the finite-difference method, in the sense that not all mesh lines need to terminate at the domain boundary. The mesh lines may end at a side of a mesh line such that the mesh consists of a collection of boxes, i.e. the elements. However, numerical stability requires that at most one mesh line may terminate at the side of a box. Therefore mesh refinement still generates a number of spurious points. The issue of the numerical stability can be traced to the five-point finite difference rule that is furthermore exploited during the refinement.
The finite-element method is a very popular method because of its high flexibility to cover domains of arbitrary shapes with triangles. The choice in favor of triangles is motivated by the fact that each triangle has three nodes and with three points one can parameterize an arbitrary linear function of two variables, i.e. over the element the solution is written as
"psgr"(x,y)=a+b.x+c.y
In three dimensions one needs four points, i.e. the triangle becomes a tetrahedron. The assembling strategy is also element by element. Sometimes for CPU time saving reasons, one performs a geometrical preprocessing such that the assembling is done link-wise, but this does not effect the element-by-element discretization and assembling. The disadvantage is that programming requires a lot of work in order to allow for submission of arbitrary complicated domains. Furthermore, adaptive meshing is possible but obtuse triangles are easily generated and one must include algorithms to repair these deficiencies, since numerical stability and numerical correctness suffers from obtuse triangles. As a consequence, mesh refinement and in particular adaptive meshing, generates in general spurious nodes.
The finite-element method is not restricted to triangles in a plane. Rectangles (and cubes in three dimensions) have become popular. However, the trial functions are always selected in such a way that a unique value is obtained on the interface. This restriction makes sense for representing scalar functions "psgr"(x,y) on a plane
In the box-integration method, each node is associated with an area (volume) being determined by the nodes located at the closest distance from this node or in other words, the closest neighbouring node in each direction. Next, the flux divergence equation is converted into an integral equation and using Gauss theorem, the flux integral of the surface of each volume is set equal to the volume integral at the right hand side of the equation, i.e. equation 1 becomes             ∫              ∂                  Ω          n                      ⁢                            J          →                          (          i          )                    ·                        (                      ⅆ            →                    )                s              =            ∫              Ω        n              ⁢                  (                              S                          (              i              )                                -                                    ∂                              ρ                                  (                  i                  )                                                                    ∂              t                                      )            ⁢                        ⅆ          n                ⁢        x            
The assembling is done node-wise, i.e. for each node the surface integral is decomposed into contributions to neighboring nodes and the volume integral at the right-hand side is approximated by the volume times the nodal value. The spatial discretization of the equation then becomes             ∑      k        ⁢                  J        lk            ⁢                        ∂                      Ω            lk                                    h          lk                      =            (                        S          l                      (            i            )                          -                              ∂                          ρ              l                              (                i                )                                              t                    )        ⁢          ΔΩ      l      
The advantages/disadvantages of the method are similar as for the Finite element method because the control volumes and the finite elements are conjugate or dual meshes. Voronoi tessellation with the Delaunay algorithm is often exploited to generate the control volumes.
In an aspect of the invention a method, i.e. the so-called Cube-Assembling Method (CAM), is disclosed for locally refining a n-dimensional mesh in a predetermined domain, wherein the mesh comprises nodes and nxe2x88x921 planes connecting these nodes thereby dividing said domain in n-dimensional first elements. The domain can be almost anything ranging from at least a part of a car to at least a part of a semiconductor device. For clarification purposes, we limit the discussion here to two-dimensional domains and two-dimensional meshes. The shape of the elements depends amongst others on the coordinate system which is chosen. By applying a mesh on a domain, the domain can be introduced in a computer aided design environment for optimization purposes. Concerning the mesh, one of the issues is to perform the optimization using the appropriate amount of nodes at the appropriate location. There is a minimum amount of nodes required in order to ensure that the optimization process leads to the right solution at least within predetermined error margins. On the other hand, if the total amount of nodes increases, the complexity increases and the optimization process slows down or even can fail. Because at the start of the optimization process, the (initial) mesh usually thus not comprise the appropriate amount of nodes, additional nodes have to be created or nodes have to be removed during the optimization process. Adding nodes is called mesh refinement whereas removing nodes is called mesh coarsening. The method of the present invention succeeds in adding or removing nodes locally. The assembling is done over the elements, being e.g. squares or cubes or hypercubes dependent of the dimension of the mesh. Like the finite-box method, the CAM method is easy to program, even in higher dimensions. However, the CAM method does not suffer from the restriction that only one line may terminate at the side of a box.
According to this aspect of the invention, a method is disclosed for locally refining a n-dimensional mesh in a predetermined domain, wherein the mesh comprises nodes and nxe2x88x921 planes connecting these nodes thereby dividing said domain in n-dimensional first elements whereby each element is defined by 2n nodes, said method comprising at least the steps of:
creating a first additional node inside at least one of said first elements by completely splitting said first element in exactly 2n n-dimensional second elements in such a manner that said first additional node forms a corner node of each of said second elements which results in the replacement of said first element by said 2n n-dimensional second elements; and
creating a second additional node inside at least one of said second elements by completely splitting said second element in exactly 2n n-dimensional third elements in such a manner that said second additional node forms a corner node of each of said third elements which results in the replacement of said second element by said 2n n-dimensional third elements.
In an embodiment of the invention after the mesh is locally refined, this mesh is locally coarsened.
In another embodiment of the invention, the refinement is based on an adaptive meshing strategy.
In another aspect of the invention, a program storage device is disclosed storing instructions that when executed by a computer perform the method for locally refining a n-dimensional mesh in a predetermined domain, wherein the mesh comprises nodes and nxe2x88x921 planes connecting these nodes thereby dividing said domain in n-dimensional first elements whereby each element is defined by 2n nodes, said method comprising at least the steps of:
creating a first additional node inside at least one of said first elements by completely splitting said first element in exactly 2n n-dimensional second elements in such a manner that said first additional node forms a corner node of each of said second elements which results in the replacement of said first element by said 2n n-dimensional second elements; and
creating a second additional node inside at least one of said second elements by completely splitting said second element in exactly 2n n-dimensional third elements in such a manner that said second additional node forms a corner node of each of said third elements which results in the replacement of said second element by said 2n n-dimensional third elements.
In an aspect of the invention a method is disclosed for optimizing of a predetermined property of a n-dimensional structure, said method comprising the steps of:
creating a n-dimensional mesh on at least a part of said structure; said mesh containing nodes and nxe2x88x921 planes connecting these nodes thereby dividing said domain in n-dimensional first elements whereby each element is defined by 2n first element;
refining said n-dimensional mesh by creating a first additional node inside at least one of said first elements by completely splitting said first element in exactly 2n n-dimensional second elements in such a manner that said first additional node forms a corner node of each of said second elements which results in the replacement of said first element by said 2n n-dimensional second elements;
further refining said n-dimensional mesh by creating a second additional node inside at least one of said second elements by completely splitting said second element in exactly 2n n-dimensional third elements in such a manner that said second additional node forms a corner node of each of said third elements which results in the replacement of said second element by said 2n n-dimensional third elements; and
where said n-dimensional mesh is used to create an improved structure.
In an embodiment of the invention said structure improvements are based on extracting said property from structure characteristics, determined at a subset of said nodes of said mesh.
In a further embodiment of the invention said structure characteristics are determined by solving the partial differential equations, describing the physical behaviour of said structure, on said mesh.
One embodiment of the invention includes a method for locally refining a mesh which can be exploited for improving computer aided design methods.